Section: New Results

NFS-related results

Concerning the number field sieve algorithm for the discrete logarithm problem in prime fields, Răzvan Bărbulescu improved the theoretical complexity of the step called “individual logarithm”, using, at a crucial point, a sequence of ECM steps with well-tuned, increasing parameters. He also proved that an approach similar to Coppersmith's factoring factory was feasible as well for discrete logarithm, yielding an improved overall complexity if heavy precomputations are allowed [21] .

In 2010, Thomas Prest and Paul Zimmermann developed a new algorithm for the polynomial selection in the Number Field Sieve (NFS). This algorithm produces two non-linear polynomials, extending Montgomery's “two quadratics” method. For degree 3, it gives two skewed polynomials with resultant $O\left(N^{5/4}\right)$, which improves on Williams $O\left(N^{4/3}\right)$ recent result. The paper will appear in the Journal of Symbolic Computation [13] and its impact is assessed by the fact that two preprints extending and analyzing the algorithm have already been proposed.